public class test {
    //leetcode 560.和为K的子数组
    class Solution {
        public static int subarraySum(int[] nums, int k) {
            int len = nums.length;
            int number = 0;
            int num = 0;
            HashMap<Integer,Integer> map = new HashMap<>();
            map.put(0,1);
            for(int i = 0;i < len;i++){
                //记录前缀和
                num += nums[i];
                //count存储[当前前缀和 - k]
                //如果map中存在等于count的前缀和
                //则代表另一部分等于k
                number += map.getOrDefault(num - k,0);
                map.put(num,map.getOrDefault(num,0) + 1);
            }
            return number;
        }
    }
    //leetcode 974.和可被K整除的子数组
    class Solution {
        public int subarraysDivByK(int[] nums, int k) {
            //前缀和与条件符合的子数组个数
            int sum = 0;
            int number = 0;
            HashMap<Integer,Integer> map = new HashMap<>();
            //用于匹配整个前缀和可被k整除的情况
            map.put(0,1);
            for(int i = 0;i < nums.length;i++){
                sum += nums[i];
                //解决[负数取余为负数]的情况
                int count = (sum % k + k) % k;
                number += map.getOrDefault(count,0);
                map.put(count,map.getOrDefault(count,0) + 1);
            }
            return number;
        }
    }
    //leetcode 525.连续数组
    class Solution {
        public int findMaxLength(int[] nums) {
            int sum = 0;
            int max = 0;
            HashMap<Integer,Integer> map = new HashMap<>();
            map.put(0,-1);
            for(int i = 0;i < nums.length;i++){
                if(nums[i] == 1){
                    sum++;
                }else {
                    sum--;
                }
                if(map.containsKey(sum)){
                    max = Math.max(max,i - map.get(sum));
                }else {
                    map.put(sum,i);
                }
            }
            return max;
        }
    }
    //leetcode 1314.矩阵区域和
    class Solution {
        public int[][] matrixBlockSum(int[][] mat, int k) {
            int row = mat.length;
            int col = mat[0].length;
            int[][] sum = new int[row+1][col+1];
            int[][] n = new int[row][col];
            for(int x = 1;x <= row;x++){
                for(int y = 1;y <= col;y++){
                    //获取二维前缀和
                    sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + mat[x - 1][y - 1];
                }
            }
            for(int x = 1;x <= row;x++){
                for(int y = 1;y <= col;y++){
                    //获取二维前缀和
                    int x1 = (x - k >= 1 ? x - k : 1);
                    int y1 = (y - k >= 1 ? y - k : 1);
                    int x2 = (x + k <= row ? x + k : row);
                    int y2 = (y + k <= col ? y + k : col);
                    n[x - 1][y - 1] = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
                }
            }
            return n;
        }
    }
    //leetcode 238.除自身以外数组的乘积
    class Solution {
        public int[] productExceptSelf(int[] nums) {
            int len = nums.length;
            int[] left = new int[len];left[0] = 1;
            int[] right = new int[len];right[len - 1] = 1;
            for(int i = 1;i < len;i++){
                left[i] = left[i - 1] * nums[i - 1];
            }
            for(int i = len - 2;i >= 0;i--){
                right[i] = right[i + 1] * nums[i + 1];
            }
            for(int i = 0;i < len;i++){
                nums[i] = left[i] * right[i];
            }
            return nums;
        }
    }

}
